#!usr/bin/env python
# -*- coding:utf8 -*-

import copy

class polynomial(object):
    def __init__(self, coefficients = None):
        if not coefficients:
            self.degree = -1
            self.coef = []
        else:
            self.degree = len(coefficients)-1
            self.coef = coefficients

    def IsZero(self):
        if self.degree == -1:
            return True
        else:
            return False

    def Coef(self, expon):
        if expon <= self.degree:
            return self.coef[self.degree - expon]
        else:
            return 0

    def LeadExp(self):
        return self.degree

    def Attach(self, coefficient, exponent):
        if exponent > self.degree:
            for i in xrange(exponent - self.degree - 1):
                self.coef.insert(0, 0)
            self.coef.insert(0, coefficient)
            self.degree = exponent
        else:
            self.coef[self.degree - exponent] = coefficient

        self.purge()

    def Remove(self, exponent):
        if exponent > self.degree:
            pass
        elif exponent == self.degree:
            self.coef.remove(0)
            self.degree -= 1
        else:
            self.coef[self.degree - exponent] = 0

        self.purge()

    def SingleMult(self, coefficient, exponent):
        self.degree += exponent
        for ico in xrange(len(self.coef)):
            self.coef[ico] *= coefficient
        self.coef.extend([0] * exponent)
        self.purge()

    def AddExpon(self, coefficient, exponent):
        if exponent > self.degree:
            self.Attach(coefficient, exponent)
        else:
            self.coef[self.degree - exponent] += coefficient

        self.purge()

    def Add(self, poly):
        for ideg in xrange(poly.degree+1):
            self.AddExpon(poly.coef[poly.degree-ideg], ideg)
        self.purge()

    def Mult(self, poly):
        oriself = polynomial()
        oriself.degree = copy.deepcopy(self.degree)
        oriself.coef = copy.deepcopy(self.coef)

        for ide in xrange(poly.degree+1):
            curoriself = polynomial()
            curoriself.degree = copy.deepcopy(oriself.degree)
            curoriself.coef = copy.deepcopy(oriself.coef)
            curoriself.SingleMult(poly.coef[poly.degree-ide], ide)
            self.Add(curoriself)
            del curoriself

        del oriself

        self.purge()

    def purge(self):
        while self.degree >= 0 and self.coef[0] == 0:
            self.coef.remove(0)
            self.degree -= 1

    def PrintPoly(self):
        str = ""
        for ide in xrange(self.degree+1):
            str += "+ %dx^%d" % (self.coef[ide], self.degree-ide)
        str = str[2:]
        print str

if __name__ == "__main__":
    coefficients  = [5,4,3,2,1]
    testpolynomial = polynomial(coefficients)
    testpolynomial.PrintPoly()
    othercoef = [23,32,34,56,4,2,1,0,6,0,8]
    newnpolynomial = polynomial(othercoef)
    testpolynomial.Add(newnpolynomial)
    testpolynomial.PrintPoly()
    testpolynomial.Mult(newnpolynomial)
    testpolynomial.PrintPoly()
